import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: LeetCode
 * @description: LeetCode : 40. 组合总和 II
 * @author: WXY
 * @create: 2023-01-18 19:23
 * @Version 1.0
 * <p>
 * 给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
 * <p>
 * candidates中的每个数字在每个组合中只能使用一次。
 * <p>
 * 注意：解集不能包含重复的组合。
 **/
public class Num040_combinationSum2 {
    public static List<List<Integer>> combinationSum2_1(int[] arr, int aim) {
        if (arr.length == 0 || arr == null || aim < 0) return new ArrayList<>();
        Arrays.sort(arr);
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> curList = new ArrayList<>();
        process(arr, 0,aim, 0, curList, list);
        return list;
    }

    private static void process(int[] arr, int index, int aim, int curSum, List<Integer> curList, List<List<Integer>> list) {

        if (curSum == aim) {
            list.add(new ArrayList<>(curList));
            return;
        }
        //每一层都已一个used 表，used[i - 1] == false，说明同一树层arr[i - 1]使用过,需要跳过
        boolean[] used = new boolean[arr.length];
        for (int i = index; i < arr.length && arr[i] + curSum <= aim; i++) {
            if (i > 0 && arr[i] == arr[i - 1] && used[i - 1] == true) continue;
            curList.add(arr[i]);
            curSum += arr[i];
            used[i] = true;
            process(arr, i + 1, aim, curSum, curList, list);
            curSum -= arr[i];
            curList.remove(curList.size() - 1);
        }
    }



    static  List<List<Integer>> list = new ArrayList<>();
    static  List<Integer> curList = new ArrayList<>();
    public static List<List<Integer>> combinationSum2(int[] arr, int aim) {
        if (arr.length == 0 || arr == null || aim < 0) return new ArrayList<>();
        Arrays.sort(arr);

        boolean[] used = new boolean[arr.length];
        process(arr, 0,aim, 0,used);
        return list;
    }

    private static void process(int[] arr, int index, int aim, int sum, boolean[] used) {
        if (sum == aim) {
            list.add(new ArrayList<>(curList));
            return;
        }
        for (int i = index; i < arr.length && arr[i] + sum <= aim; i++) {
            // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            // 要对同一树层使用过的元素进行跳过
            if (i > 0 && (arr[i] == arr[i - 1]) && (used[i - 1] == false)) {
               continue;
            }
            sum += arr[i];
            curList.add(arr[i]);
            used[i] = true;
            process(arr, i + 1, aim, sum, used);
            used[i] = false;
            sum -= arr[i];
            curList.remove(curList.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 6, 1, 5};
        List<List<Integer>> lists = combinationSum2_1(arr, 8);
        System.out.println(lists);
    }
}
